<?php
/*
 * PHP QR Code encoder Reed-Solomon error correction support Copyright (C) 2002,
 * 2003, 2004, 2006 Phil Karn, KA9Q (libfec is released under the GNU Lesser
 * General Public License.) Based on libqrencode C library distributed under
 * LGPL 2.1 Copyright (C) 2006, 2007, 2008, 2009 Kentaro Fukuchi
 * <fukuchi@megaui.net> PHP QR Code is distributed under LGPL 3 Copyright (C)
 * 2010 Dominik Dzienia <deltalab at poczta dot fm> This library is free
 * software; you can redistribute it and/or modify it under the terms of the GNU
 * Lesser General Public License as published by the Free Software Foundation;
 * either version 3 of the License, or any later version. This library is
 * distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
 * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A
 * PARTICULAR PURPOSE. See the GNU Lesser General Public License for more
 * details. You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
 */
class QRrsItem {
	public $mm; // Bits per symbol
	public $nn; // Symbols per block (= (1<<mm)-1)
	public $alpha_to = array (); // log lookup table
	public $index_of = array (); // Antilog lookup table
	public $genpoly = array (); // Generator polynomial
	public $nroots; // Number of generator roots = number of parity symbols
	public $fcr; // First consecutive root, index form
	public $prim; // Primitive element, index form
	public $iprim; // prim-th root of 1, index form
	public $pad; // Padding bytes in shortened block
	public $gfpoly;
	
	// ----------------------------------------------------------------------
	public function modnn($x) {
		while ( $x >= $this->nn ) {
			$x -= $this->nn;
			$x = ($x >> $this->mm) + ($x & $this->nn);
		}
		
		return $x;
	}
	
	// ----------------------------------------------------------------------
	public static function init_rs_char($symsize, $gfpoly, $fcr, $prim, $nroots, $pad) {
		// Common code for intializing a Reed-Solomon control block (char or int
		// symbols)
		// Copyright 2004 Phil Karn, KA9Q
		// May be used under the terms of the GNU Lesser General Public License
		// (LGPL)
		$rs = null;
		
		// Check parameter ranges
		if ($symsize < 0 || $symsize > 8)
			return $rs;
		if ($fcr < 0 || $fcr >= (1 << $symsize))
			return $rs;
		if ($prim <= 0 || $prim >= (1 << $symsize))
			return $rs;
		if ($nroots < 0 || $nroots >= (1 << $symsize))
			return $rs; // Can't
			                                                                 // have more
			                                                                 // roots
			                                                                 // than
			                                                                 // symbol
			                                                                 // values!
		if ($pad < 0 || $pad >= ((1 << $symsize) - 1 - $nroots))
			return $rs; // Too
			                                                                 // much
			                                                                 // padding
		
		$rs = new QRrsItem ();
		$rs->mm = $symsize;
		$rs->nn = (1 << $symsize) - 1;
		$rs->pad = $pad;
		
		$rs->alpha_to = array_fill ( 0, $rs->nn + 1, 0 );
		$rs->index_of = array_fill ( 0, $rs->nn + 1, 0 );
		
		// PHP style macro replacement ;)
		$NN = & $rs->nn;
		$A0 = & $NN;
		
		// Generate Galois field lookup tables
		$rs->index_of [0] = $A0; // log(zero) = -inf
		$rs->alpha_to [$A0] = 0; // alpha**-inf = 0
		$sr = 1;
		
		for($i = 0; $i < $rs->nn; $i ++) {
			$rs->index_of [$sr] = $i;
			$rs->alpha_to [$i] = $sr;
			$sr <<= 1;
			if ($sr & (1 << $symsize)) {
				$sr ^= $gfpoly;
			}
			$sr &= $rs->nn;
		}
		
		if ($sr != 1) {
			// field generator polynomial is not primitive!
			$rs = NULL;
			return $rs;
		}
		
		/* Form RS code generator polynomial from its roots */
		$rs->genpoly = array_fill ( 0, $nroots + 1, 0 );
		
		$rs->fcr = $fcr;
		$rs->prim = $prim;
		$rs->nroots = $nroots;
		$rs->gfpoly = $gfpoly;
		
		/* Find prim-th root of 1, used in decoding */
		for($iprim = 1; ($iprim % $prim) != 0; $iprim += $rs->nn)
			; // intentional empty-body loop!
		
		$rs->iprim = ( int ) ($iprim / $prim);
		$rs->genpoly [0] = 1;
		
		for($i = 0, $root = $fcr * $prim; $i < $nroots; $i ++, $root += $prim) {
			$rs->genpoly [$i + 1] = 1;
			
			// Multiply rs->genpoly[] by @**(root + x)
			for($j = $i; $j > 0; $j --) {
				if ($rs->genpoly [$j] != 0) {
					$rs->genpoly [$j] = $rs->genpoly [$j - 1] ^ $rs->alpha_to [$rs->modnn ( $rs->index_of [$rs->genpoly [$j]] + $root )];
				} else {
					$rs->genpoly [$j] = $rs->genpoly [$j - 1];
				}
			}
			// rs->genpoly[0] can never be zero
			$rs->genpoly [0] = $rs->alpha_to [$rs->modnn ( $rs->index_of [$rs->genpoly [0]] + $root )];
		}
		
		// convert rs->genpoly[] to index form for quicker encoding
		for($i = 0; $i <= $nroots; $i ++)
			$rs->genpoly [$i] = $rs->index_of [$rs->genpoly [$i]];
		
		return $rs;
	}
	
	// ----------------------------------------------------------------------
	public function encode_rs_char($data, &$parity) {
		$MM = & $this->mm;
		$NN = & $this->nn;
		$ALPHA_TO = & $this->alpha_to;
		$INDEX_OF = & $this->index_of;
		$GENPOLY = & $this->genpoly;
		$NROOTS = & $this->nroots;
		$FCR = & $this->fcr;
		$PRIM = & $this->prim;
		$IPRIM = & $this->iprim;
		$PAD = & $this->pad;
		$A0 = & $NN;
		
		$parity = array_fill ( 0, $NROOTS, 0 );
		
		for($i = 0; $i < ($NN - $NROOTS - $PAD); $i ++) {
			
			$feedback = $INDEX_OF [$data [$i] ^ $parity [0]];
			if ($feedback != $A0) {
				// feedback term is non-zero
				
				// This line is unnecessary when GENPOLY[NROOTS] is unity, as it
				// must
				// always be for the polynomials constructed by init_rs()
				$feedback = $this->modnn ( $NN - $GENPOLY [$NROOTS] + $feedback );
				
				for($j = 1; $j < $NROOTS; $j ++) {
					$parity [$j] ^= $ALPHA_TO [$this->modnn ( $feedback + $GENPOLY [$NROOTS - $j] )];
				}
			}
			
			// Shift
			array_shift ( $parity );
			if ($feedback != $A0) {
				array_push ( $parity, $ALPHA_TO [$this->modnn ( $feedback + $GENPOLY [0] )] );
			} else {
				array_push ( $parity, 0 );
			}
		}
	}
}

// ##########################################################################
class QRrs {
	public static $items = array ();
	
	// ----------------------------------------------------------------------
	public static function init_rs($symsize, $gfpoly, $fcr, $prim, $nroots, $pad) {
		foreach ( self::$items as $rs ) {
			if ($rs->pad != $pad)
				continue;
			if ($rs->nroots != $nroots)
				continue;
			if ($rs->mm != $symsize)
				continue;
			if ($rs->gfpoly != $gfpoly)
				continue;
			if ($rs->fcr != $fcr)
				continue;
			if ($rs->prim != $prim)
				continue;
			
			return $rs;
		}
		
		$rs = QRrsItem::init_rs_char ( $symsize, $gfpoly, $fcr, $prim, $nroots, $pad );
		array_unshift ( self::$items, $rs );
		
		return $rs;
	}
}